/*******************************************************************************
 * Witz - Winboard Chess Engine                                                *
 * SEARCH.C                                                                    *
 *                                                                             *
 * The search engine for Witz                                                  *
 *                                                                             *
 * Please refer to the licence notice in MAIN.C                                *
 *                                                                             *
 * Copywright (C) 2006 Pradu Kannan                                            *
 * http://witz.sf.net/                                                         *
 ******************************************************************************/

#include <windows.h>


#include "build.h"
#include "defs.h"
#include "protos.h"
#include "data.h"
#include "threads.h"
#ifdef DEBUGSEARCH
	#include "debug.h"
#endif


/*Messy longjump to support timed controlls
 *this was done so that Witz Alpha 18 could be released at the scheduled time
 *It will be removed and replaced with neater threaded timecontrol*/
/*================REMOVE==================*/
#include <setjmp.h>
jmp_buf env;
bool stopSearch;
/*================REMOVE==================*/

int depthLimit=INITIAL_DEPTH_LIMIT;
U64 nodes;
U64 leafNodes;
char searchFlag;

bool threaded = true;

/*getBestMove()
 *gets the best move for the current board position
 *
 *@param depth - the depth to search up to (INF for timed controlls)
 *
 *@returns the best move to be played
 */
move getBestMove(void* depth)
{
	int d,i;
	move m;
	TTprobe tt_probe;
	bool tt_hit;
	startClock();
	resetHH();
	resetKillers();
	nodes=0;

	if(mainMoveList.moveCount==1)
		return mainMoveList.moves->m;
	if((m=getBookMove())!=NULLMOVE)
		return m;
	/*================REMOVE==================*/
	stopSearch=false;
	setjmp(env);
	if(stopSearch)
	{
		tt_hit=probeTT(&mainboard,&tt_probe);
		if(tt_hit && tt_probe.m!=NULLMOVE)
			return tt_probe.m;
		//should never get here
		printf("Fatal Error - root move not found in Transposition Table\n");
		return m;
	}
	/*================REMOVE==================*/

	#ifdef DEBUG_DUMPSTATE
		dumpState();
	#endif

	#ifdef DEBUGSEARCH
		openDebugFile();
	#endif

	for(d=1;d<=*((int*)depth);d++)
	{
		#ifdef DEBUGSEARCH
			fprintf(debugfile,"\nDepth%d\n",d);
		#endif
 		if(searchType==PVS)
			m=pvsStart(NEGINF,INF,d).m;
		else //otherwise do alphabeta
			m=alphabetaStart(NEGINF,INF,d).m;
		//find hashed move and put it in front
		tt_hit=probeTT(&mainboard,&tt_probe);
		if(tt_hit && tt_probe.m!=NULLMOVE)
			for(i=0;i<mainMoveList.moveCount;i++)
				if(mainMoveList.moves[i].m==tt_probe.m)
				{
					mainMoveList.moves[i].score=INF;
				}
				else if(mainMoveList.moves[i].score==INF)
					mainMoveList.moves[i].score=INF-1;
		sort(&mainMoveList);
	}
	#ifdef DEBUGSEARCH
		closeDebugFile();
	#endif
	tt_hit=probeTT(&mainboard,&tt_probe);
	if(tt_hit && tt_probe.m!=NULLMOVE)
		return tt_probe.m;
	//should never get here
	printf("Fatal Error - root move not found in Transposition Table\n");
	return m;
}

/*ponder()
 *fills the hash table up with useful entries when not on move
 */
void ponder(){};

/*perft()
 *particular type of search used to test the move generation and tree traversal
 *code in Witz
 *
 *@param d - depth to search up to
 *
 *@returns the number of nodes traversed as a 64bit number
 */
U64  perft(const char d)
{
	int i;
	depth=0;
	nodes=U64EMPTY;
	leafNodes=U64EMPTY;
	for(i=0;i<mainMoveList.moveCount;i++)
		perftHelper(mainboard,mainMoveList.moves[i].m,d-1);
	return leafNodes;
}
void perftHelper(board pos, const move m, const char d)
{
	int i;
	moveList moveChoices;
	nodes++;
	if(makemove(&pos,m))
		return;
	if(!d)
	{
		leafNodes++;
		return;
	}
	generatePerftMoves(&pos,&moveChoices);
	for(i=0;i<moveChoices.moveCount;i++)
		perftHelper(pos,moveChoices.moves[i].m,d-1);
	return;
}

/*pvsStart()
 *a fail-soft pvs search algorithm that starts pvs from the mainboard
 *also prints pv when needed
 *
 *@param alpha - lower bound (usually -INF)
 *@param beta  - upper bound (usually  INF)
 *@param depth - the depth left to search
 *
 *@returns the best scored move for the position for the specified depth
 */
smove pvsStart(int alpha, int beta, short depth)
{
	smove smov;
	short i;
	U8 hashFlag=ALPHA;
	bool do_mws=false; //do minimal window search
	int lwb,upb;
	drawEntry drawTable[MAX_PLY];
	smov.m=mainMoveList.moves[0].m;
	smov.score=alpha;

	drawTable->fiftyReset=(mainboard.fifty==0);
	drawTable->hashkey=mainboard.hashkey;

	for(i=0;i<mainMoveList.moveCount;i++)
	{
		//derive bounds and perform the recursive PVS call
		lwb=max(alpha,smov.score);
		upb=do_mws?lwb+1:beta;
		mainMoveList.moves[i].score=-pvs(-upb,-lwb,mainMoveList.moves[i].m,mainboard,depth-1,1,drawTable);
		//re-search if the minimal window search fails high (new best score found)
		if(do_mws && lwb<mainMoveList.moves[i].score && mainMoveList.moves[i].score<beta)
			mainMoveList.moves[i].score=-pvs(-beta,-mainMoveList.moves[i].score+1,mainMoveList.moves[i].m,mainboard,depth-1,1,drawTable);
		if(mainMoveList.moves[i].score>smov.score)
		{
			smov=mainMoveList.moves[i];
			if(smov.score>=alpha)
			{
				hashFlag=EXACT;
				do_mws=true;
			}
			//recording here is safe to do because all coming positions will be decided as drawn
			recordTT(&mainboard,smov.m,smov.score,hashFlag,depth,0);
			if(Post)
			{
				printf("%d %d %d %d ",depth,smov.score,(getms()-startTime)/10,nodes);
				printPV();
				printf("\n");
			}
		}
	}
	recordTT(&mainboard,smov.m,smov.score,hashFlag,depth,0);
	if(Post)
	{
		printf("%d %d %d %d ",depth,smov.score,(getms()-startTime)/10,nodes);
		printPV();
		printf("\n");
	}
	//ICS output
	if(ICS && (endTime-(double)getms())/(endTime-startTime)<ICS_PV)
	{
		printf("tellothers Depth:%d Score:%d PV:",smov.score,depth);
		printPV();
		printf("\n");
	}
	updateHH(smov.m,depth);
	return smov;
}

/*pvs()
 *a fail-soft pvs search algorithm
 *
 *@param alpha     - lower bound
 *@param beta      - upper bound
 *@param m         - move to be made on parent position
 *@param pos       - the parent position (copy by value)
 *@param depth     - the depth left to search
 *@param dfr       - depth from root
 *@param drawTable - the 3-move repetition draw table
 *
 *@returns the search score for the position for the specified depth
 */
int pvs(int alpha, int beta, move m, board pos, short depth, short dfr, drawEntry* drawTable)
{
	int i,illegalMoves=0;
	smove best; //keeps track of best move and score
	moveList moveChoices;
	U8 hashFlag=ALPHA;
	TTprobe tt_probe;
	bool tt_hit;
	bool do_mws=false; //do minimal window search
	int lwb,upb;
	nodes++;

	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	if(makemove(&pos,m)) //execute opponent's move
		return INF; //if move is illegal


	//update drawTable
	drawTable[dfr].fiftyReset=(extractPiece(m)==P || extractCapture(m))?true:false;
	drawTable[dfr].hashkey=pos.hashkey;

	//test stop conditions

	if(decidable(&pos,drawTable,dfr,&i))
		return i;

	//Extensions if in check or the move is a recapture or if a pawn move to 7th
	if(inCheck(pos,pos.side)
		|| recaptureExtensions && extractSFRecapture(pos.SF)==extractCapture(m) && extractSFRecapture(pos.SF)
		|| (extractPiece(m)==P && rank7[pos.xside]&toBit[extractTo(m)]))
		depth++;


	//extension if there the move was a pawn move to the seventh rank


	best.score=NEGINF;

	//Transposition Table

	tt_hit=probeTT(&pos,&tt_probe);
	if(tt_hit)
	{
		//test the applicability of the cached score information
		if(depth<=tt_probe.depth)
		{
			//handle transposition-table results that are exact scores
			if(tt_probe.flag==EXACT)
				return tt_probe.score;
			//handle transposition-table results that are upper bounds
			else if(tt_probe.flag==ALPHA)
			{
				if(tt_probe.score<=alpha) return tt_probe.score;
				//lower beta and the best upper bound so far
				if(tt_probe.score<beta) beta=tt_probe.score;
				//if(tt_score<upper) upper=tt_score;
			}
			//handle transposition-table results that are lower bounds
			else if(tt_probe.flag==BETA)
			{
				//trasposition table fail-high cutoffs
				if(tt_probe.score>=beta) return tt_probe.score;
				//raise alpha and best score so far
				if(tt_probe.score>alpha) alpha=tt_probe.score;
				//if(tt_probe.score>best.score) best.score=tt_probe.score;
			}
		}
	}
	//else {...} entry not found in transposition tables

	//eval
	if(depth<=0)
	{
		best.score=ABhorizonScore(alpha, beta, &pos);
		best.m = NULLMOVE;
		if(best.score>=beta)
			recordTT(&pos,best.m,best.score,BETA,0,dfr);
		else if(best.score<alpha)
			recordTT(&pos,best.m,best.score,ALPHA,0,dfr);
		else
			recordTT(&pos,best.m,best.score,EXACT,0,dfr);
		return best.score;
	}

	//try nullmove
	if(tryNull(&pos,tt_hit,&tt_probe,depth))
	{
		//don't try null if the data in the trasposition table has that accuracy and score < beta
		//if(tt_hit && tt_probe.depth>=(depth-adaptiveR(&pos,depth)))
		//	goto nullend;
		i=-pvs(-beta,-beta+1,NULLMOVE,pos,depth-adaptiveR(&pos,depth)-1,dfr+1,drawTable);
		//test for potential fail-high null-move cuttoff
		if(i>=beta) return i;
	}
//nullend:

	generateMoves(&pos,&moveChoices); //generate moves

	if(moveChoices.moveCount==0) //if there are no moves to make
		return 0;                //return a draw score

	//find killer move
	for(i=0;i<moveChoices.moveCount;i++)
		if(moveChoices.moves[i].m==killers[dfr])
		{
			moveChoices.moves[i].score=KILLERVAL;
			break;
		}
	//find hashed move and put it in the front
	if(tt_hit && tt_probe.m!=NULLMOVE)
		for(i=0;i<moveChoices.moveCount;i++)
			if(moveChoices.moves[i].m==tt_probe.m)
			{
				moveChoices.moves[i].score=INF;
				break;
			}
	sort(&moveChoices);

	for(i=0;i<moveChoices.moveCount;i++) //try each move and see if it is better than the previous ones
	{
		//derive bounds and perform the recursive PVS call
		lwb=max(alpha,best.score);
		upb=do_mws?lwb+1:beta;
		moveChoices.moves[i].score=-pvs(-upb,-lwb,moveChoices.moves[i].m,pos,depth-1,dfr+1,drawTable);
		if(moveChoices.moves[i].score==NEGINF)
		{
			illegalMoves++;
			continue;
		}

		//re-search if the minimal window search fails high (new best score found)
		if(do_mws && lwb<moveChoices.moves[i].score && moveChoices.moves[i].score<beta)
			moveChoices.moves[i].score=-pvs(-beta,-moveChoices.moves[i].score+1,moveChoices.moves[i].m,pos,depth-1,dfr+1,drawTable);

		if(moveChoices.moves[i].score>best.score)
		{
			if(best.score>=alpha)
			{
				do_mws=true;
				hashFlag=EXACT;
			}
			best=moveChoices.moves[i];
		}
		if(best.score>=beta)
		{
			recordTT(&pos,best.m,best.score,BETA,depth,dfr);
			updateHH(best.m,depth);
			updateKiller(best.m,dfr);
			return best.score;
		}
	}
	if(illegalMoves==moveChoices.moveCount)
	{
		if(inCheck(pos,pos.side))
			return -(MATE-dfr);
		return 0;
	}
	recordTT(&pos,best.m,best.score,hashFlag,depth,dfr);
	updateHH(best.m,depth);
	return best.score;
}


/*horizonScore()
 *starts quiescence search
 *
 *@param alpha - lower bound
 *@param beta  - upper bound
 *@param m     - move to be made on parent position
 *@param pos   - the parent position (copy by value)
 *
 *@returns the quiescence search score for the position
 */
int horizonScore(int alpha, int beta, board* pos)
{
	int i, score, val;
	moveList moveChoices;
	int lwb,upb;

	score=eval(pos);
	if(score>=beta) // test for "stand pat" cuttoff
		return score;
	if(score+Qval>=alpha) // Delta pruning
		return alpha;
	generateGoodCaptures(pos,&moveChoices);
	if(moveChoices.moveCount==0)
		return score;
	//follow promising captures
	for(i=0;i<moveChoices.moveCount;i++)
	{
		//Selective Futility Condition (material_balance+SEE(m)+qs_futility_margin <=alpha)
		/*if(pos->material + moveChoices.moves[i].score + QS_FUTIL_MARGIN <= alpha)
			break;*/
		//do minimal window search only if the move is not the first move
		//and if the first move dosen't have a positive move ordering score
		if(i || moveChoices.moves[0].score<=0)
		{
			//derive bounds and perform the recursive PVS call
			lwb=max(alpha,score);
			upb=lwb+1;
			val=-qsearch(-upb,-lwb,moveChoices.moves[i].m,*pos);
			//re-search if the minimal window search fails high (new best score found)
			if((lwb<val) && (val<beta))
				val=-qsearch(-beta,-val+1,moveChoices.moves[i].m,*pos);
		}
		else //otherwise no minimal window
			val=-qsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,*pos);
		if(val>score) score=val;
		if(score>=beta) return score;
	}
	return score;
}

/*qsearch()
 *a quiescence search which makes sure we have a quiet position to score
 *
 *@param alpha - lower bound
 *@param beta - upper bound
 *@param caputre - a capture move
 *@param pos - the parent board position
 *
 *@returns the move's quiesce score
 */
int qsearch(int alpha, int beta, move capture, board pos)
{
	int i;
	moveList moveChoices;
	int score, val;
	int lwb,upb;

	nodes++;

	if(makemove(&pos,capture)) //execute opponents caputre
		return INF; //return if illegal
	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	if(decidable(&pos,(drawEntry*)NULL,-1,&i)) //test the game-theoretical decidability of the current position
		return i;
	if(checkEvasions && inCheck(pos,pos.side))
		checkEvasion(alpha,beta,&pos);
	score=eval(&pos);
	if(score>=beta) // test for "stand pat" cuttoff
		return score;
	generateGoodCaptures(&pos,&moveChoices);
	if(moveChoices.moveCount==0)
		return score;
	//follow promising captures
	for(i=0;i<moveChoices.moveCount;i++)
	{
		//Selective Futility Condition (material_balance+SEE(m)+qs_futility_margin <=alpha)
		/*if(pos->material + moveChoices.moves[i].score + QS_FUTIL_MARGIN <= alpha)
			break;*/
		//do minimal window search only if the move is not the first move
		//and if the first move dosen't have a positive move ordering score
		if(i || moveChoices.moves[0].score<=0)
		{
			//derive bounds and perform the recursive PVS call
			lwb=max(alpha,score);
			upb=lwb+1;
			val=-qsearch(-upb,-lwb,moveChoices.moves[i].m,pos);
			//re-search if the minimal window search fails high (new best score found)
			if((lwb<val) && (val<beta))
				val=-qsearch(-beta,-val+1,moveChoices.moves[i].m,pos);
		}
		else //otherwise no minimal window
			val=-qsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,pos);
		if(val>score) score=val;
		if(score>=beta) return score;
	}
	return score;
}

/*checkEvasion()
 *does a checkevasion search
 *
 *@param pos   - the board position
 *@param alpha - lower bound (usually -INF)
 *@param beta  - upper bound (usually  INF)
 *
 *@returns the best scored move for the position for the specified depth
 */
int checkEvasion(int alpha, int beta, board *pos)
{
	int i,illegalMoves=0;
	moveList moveChoices;
	int score=NEGINF,temp;
	nodes++;
	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	generateMoves(pos,&moveChoices);
	sort(&moveChoices);
	if(moveChoices.moveCount==0)
		return 0;
	for(i=0;i<moveChoices.moveCount;i++)
	{
		temp=-qsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,*pos);
		if(temp==NEGINF)
		{
			illegalMoves++;
			continue;
		}
		score=max(score,temp);
		if(score>=beta) return score;
	}
	if(illegalMoves==moveChoices.moveCount)
		return -(MATE-999);
	return score;
}

/*tryNull()
 *tells the search whether to try a null move or not
 *
 *@param pos - the board position in the search
 *
 *@returns whether to try a null move or not
 */
bool tryNull(const board* pos, const bool tt_hit, const TTprobe* tt_probe, const short depth)
{
	if(extractSFNull(pos->SF) || inCheck(*pos,pos->side))
		return false;
	if(tt_hit && (tt_probe->flag==ALPHA || tt_probe->flag==EXACT) && ((depth-adaptiveR(pos, depth))<=tt_probe->depth))
		return false;
	if(popCount(pos->Pieces[N]|pos->Pieces[B]|pos->Pieces[R]|pos->Pieces[Q]) < 4)
		return false;
	return true;
}

/*adaptiveR()
 *gets the adaptive depth reduction factor for adaptive nullmove pruning
 *R is always 3 for verified nullmove pruning
 *
 *@param pos - the board position
 *@param d   - the depth left
 *
 *@returns the depth reduction factor
 */
U16 adaptiveR(const board* pos, const short d)
{
	U64 pieces=pos->PieceTypes[N]&pos->PieceTypes[B]&pos->PieceTypes[Q]&pos->PieceTypes[R];
	int maxPiecesPerSide=max(popCount(pieces&pos->PiecesSide[WHITE]),popCount(pieces&pos->PiecesSide[BLACK]));
	return 2 + ((d) > (6 + ((maxPiecesPerSide<3)?2:0)));
}

/*max()
 *returns the the larger value, a or b
 *an optimizing compiler is automatically supposed to inline this
 *
 *@param a - a value
 *@param b - a value
 *
 *@returns the larger value
 */
int max(int a, int b)
{
	if(a>b) return a;
	else return b;
}

/*min()
 *returns the the smaller value, a or b
 *
 *@param a - a value
 *@param b - a value
 *
 *@returns the smaller value
 */
int min(int a, int b)
{
	if(a<b) return a;
	else return b;
}

/*******************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************** ALPHABETA ALGORITHM FOR REFERENCE ***********************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
*******************************************************************************/

/*alphabetaStart()
 *a fail-soft alphabeta search algorithm that starts alphabeta from the mainboard
 *also prints pv when needed
 *
 *@param alpha - lower bound (usually -INF)
 *@param beta  - upper bound (usually  INF)
 *@param depth - the depth left to search
 *
 *@returns the best scored move for the position for the specified depth
 */
smove alphabetaStart(int alpha, int beta, short depth)
{
	int waitingRequests=0;
	ThreadParams *params;

	smove smov;

	int i;
	U8 hashFlag=ALPHA;
	drawEntry drawTable[MAX_PLY];
	smov.m=mainMoveList.moves[0].m;
	smov.score=alpha;
	drawTable->fiftyReset=(mainboard.fifty==0);
	drawTable->hashkey=mainboard.hashkey;
	
	if(!threaded)
		for(i=0;i<mainMoveList.moveCount;i++)
		{
			#ifdef DEBUGSEARCH
				addDebugMove(mainMoveList.moves[i].m);
				printPositionToFile(&mainMoveList,alpha, beta, smov.score,true);
			#endif
			mainMoveList.moves[i].score=-alphabeta(-beta,-max(alpha,smov.score),mainMoveList.moves[i].m,mainboard,depth-1,1,drawTable);
			#ifdef DEBUGSEARCH
				printPositionToFile(&mainMoveList,alpha, beta, smov.score,false);
				removeDebugMove();
			#endif
			if(mainMoveList.moves[i].score>smov.score)
			{
				smov=mainMoveList.moves[i];
				if(smov.score>=alpha)
					hashFlag=EXACT;
				//recording here is safe to do because all coming positions will be decided as drawn
				recordTT(&mainboard,smov.m,smov.score,hashFlag,depth,0);
				if(Post)
				{
					printf("%d %d %d %d ",depth,smov.score,(getms()-startTime)/10,nodes);
					printPV();
					printf("\n");
				}
			}
		}
	else
	{
		i=0;
		while(i<mainMoveList.moveCount || waitingRequests>0)
		{
			if(i<mainMoveList.moveCount)
			{
				params = malloc(sizeof(ThreadParams));
				params->i=i;
				params->alpha=max(alpha, smov.score);
				params->beta=beta;
				params->depth=depth;
				params->drawTable=drawTable;
				params->m=mainMoveList.moves[i].m;

				AddToQueue(&operationQueue, params);
				waitingRequests++;
				i++;
			}
			
			if(i==mainMoveList.moveCount || resultQueue.size>0 || i<sti)
			{
				params = RemoveFromQueue(&resultQueue);
				waitingRequests--;
				
				if(mainMoveList.moves[params->i].score>smov.score)
				{
					smov=mainMoveList.moves[params->i];
					if(smov.score>=alpha)
						hashFlag=EXACT;
					//recording here is safe to do because all coming positions will be decided as drawn
					recordTT(&mainboard,smov.m,smov.score,hashFlag,depth,0);
					if(Post)
					{
						printf("%d %d %d %d ",depth,smov.score,(getms()-startTime)/10,nodes);
						printPV();
						printf("\n");
					}
				}

				free(params);
			}
		}
	}

	recordTT(&mainboard,smov.m,smov.score,hashFlag,depth,0);
	if(Post)
	{
		printf("%d %d %d %d ",depth,smov.score,(getms()-startTime)/10,nodes);
		printPV();
		printf("\n");
	}
	//ICS output
	if(ICS && (endTime-(double)getms())/(endTime-startTime)<ICS_PV)
	{
		printf("tellothers Score:%d Depth:%d PV:",smov.score,depth);
		printPV();
		printf("\n");
	}
	updateHH(smov.m,depth);
	return smov;
}

/*alphabeta()
 *a fail-soft alphabeta search algorithm
 *
 *@param alpha     - lower bound
 *@param beta      - upper bound
 *@param m         - move to be made on parent position
 *@param pos       - the parent position (copy by value)
 *@param depth     - the depth left to search
 *@param dfr       - depth from root
 *@param drawTable - the 3-move repetition draw table
 *
 *@returns the search score for the position for the specified depth
 */
int alphabeta(int alpha, int beta, move m, board pos, short depth, short dfr, drawEntry* drawTable)
{
	int i,illegalMoves=0;
	smove best; //keeps track of best move and score
	moveList moveChoices;
	U8 hashFlag=ALPHA;
	TTprobe tt_probe;
	bool tt_hit;
	bool fail_high=false;
	nodes++;
	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	if(makemove(&pos,m)) //execute opponent's move
		return INF; //if move is illegal

	//update drawTable
	drawTable[dfr].fiftyReset=(extractPiece(m)==P || extractCapture(m))?true:false;
	drawTable[dfr].hashkey=pos.hashkey;

	//test stop conditions

	if(decidable(&pos,drawTable,dfr,&i))
		return i;

	//Extensions if in check or the move is a recapture or if a pawn move to 7th
	if(inCheck(pos,pos.side)
		|| recaptureExtensions && extractSFRecapture(pos.SF)==extractCapture(m) && extractSFRecapture(pos.SF)
		|| (extractPiece(m)==P && rank7[pos.xside]&toBit[extractTo(m)]))
		depth++;

	best.score=NEGINF;

	//Transposition Table

	tt_hit=probeTT(&pos,&tt_probe);
	if(tt_hit)
	{
		//test the applicability of the cached score information
		if(depth<=tt_probe.depth)
		{
			//handle transposition-table results that are exact scores
			if(tt_probe.flag==EXACT)
				return tt_probe.score;
			//handle transposition-table results that are upper bounds
			else if(tt_probe.flag==ALPHA)
			{
				if(tt_probe.score<=alpha) return tt_probe.score;
				//lower beta and the best upper bound so far
				if(tt_probe.score<beta) beta=tt_probe.score;
				//if(tt_score<upper) upper=tt_score;
			}
			//handle transposition-table results that are lower bounds
			else if(tt_probe.flag==BETA)
			{
				//trasposition table fail-high cutoffs
				if(tt_probe.score>=beta) return tt_probe.score;
				//raise alpha and best score so far
				if(tt_probe.score>alpha) alpha=tt_probe.score;
				//if(tt_probe.score>best.score) best.score=tt_probe.score;
			}
		}
	}
	//else {...} entry not found in transposition tables

	//eval
	if(depth<=0)
	{
		best.score=ABhorizonScore(alpha, beta, &pos);
		best.m = NULLMOVE;
		if(best.score>=beta)
			recordTT(&pos,best.m,best.score,BETA,0,dfr);
		else if(best.score<alpha)
			recordTT(&pos,best.m,best.score,ALPHA,0,dfr);
		else
			recordTT(&pos,best.m,best.score,EXACT,0,dfr);
		return best.score;
	}

	//make sure a nullmove is desirable in the position
	if(tryNull(&pos,tt_hit,&tt_probe,depth))
	{
		//don't try null if the data in the trasposition table has that accuracy
		/*if(tt_hit && tt_probe.depth>=(depth-adaptiveR(&pos,depth)))
			goto nullend;*/
		i=-alphabeta(-beta,-beta+1,NULLMOVE,pos,depth-adaptiveR(&pos,depth)-1,dfr+1,drawTable);
		if(i>=beta) return i;
	}

	generateMoves(&pos,&moveChoices); //generate moves

	if(moveChoices.moveCount==0) //if there are no moves to make
		return 0;                //return a draw score

	//find killer move
	for(i=0;i<moveChoices.moveCount;i++)
		if(moveChoices.moves[i].m==killers[dfr])
		{
			moveChoices.moves[i].score=KILLERVAL;
			break;
		}
	//find hashed move and put it in the front
	if(tt_hit && tt_probe.m!=NULLMOVE)
		for(i=0;i<moveChoices.moveCount;i++)
			if(moveChoices.moves[i].m==tt_probe.m)
			{
				moveChoices.moves[i].score=INF;
				break;
			}
	sort(&moveChoices);

//re_search: //if a zugzwang is detected, return here for re-search

	for(i=0;i<moveChoices.moveCount;i++) //try each move and see if it is better than the previous ones
	{
		#ifdef DEBUGSEARCH
			addDebugMove(moveChoices.moves[i].m);
			printPositionToFile(&moveChoices,alpha, beta, best.score,true);
		#endif
		moveChoices.moves[i].score=-alphabeta(-beta,-max(alpha,best.score),moveChoices.moves[i].m,pos,depth-1,dfr+1,drawTable);
		#ifdef DEBUGSEARCH
			printPositionToFile(&moveChoices,alpha, beta, best.score,false);
			removeDebugMove();
		#endif
		if(moveChoices.moves[i].score==NEGINF)
		{
			illegalMoves++;
			continue;
		}
		if(moveChoices.moves[i].score>best.score)
		{
			if(best.score>=alpha)
				hashFlag=EXACT;
			best=moveChoices.moves[i];
		}
		if(best.score>=beta)
		{
			recordTT(&pos,best.m,best.score,BETA,depth,dfr);
			updateHH(best.m,depth);
			updateKiller(best.m,dfr);
			return best.score;
		}
	}
	if(illegalMoves==moveChoices.moveCount)
	{
		if(inCheck(pos,pos.side))
			return -(MATE-dfr);
		return 0;
	}

	/*if there is a fail-high report from the nullmove but no cutoff was found,
	 *the position is a zugzwang and has to be re-searched with orignal depth */
	/*if(fail_high && best.score<beta)
	{
		depth++;
		best.score=NEGINF;
		fail_high=false;
		pos.SF^=encodeSFNoVerify;
		printf("gets here\n");
		goto re_search;
	}*/

	recordTT(&pos,best.m,best.score,hashFlag,depth,dfr);
	updateHH(best.m,depth);
	return best.score;
}


/*ABhorizonScore()
 *starts quiescence search
 *
 *@param alpha - lower bound
 *@param beta  - upper bound
 *@param m     - move to be made on parent position
 *@param pos   - the position
 *
 *@returns the quiescence search score for the position
 */
int ABhorizonScore(int alpha, int beta, const board* pos)
{
	int i;
	moveList moveChoices;
	int score;
	score=eval(pos);
	if(score>=beta) // test for "stand pat" cuttoff
		return score;
	generateGoodCaptures(pos,&moveChoices);
	if(moveChoices.moveCount==0)
		return score;
	//follow promising captures
	for(i=0;i<moveChoices.moveCount;i++)
	{
		//Selective Futility Condition (material_balance+SEE(m)+qs_futility_margin <=alpha)
		/*if(pos->material + moveChoices.moves[i].score + QS_FUTIL_MARGIN <= alpha)
			break;*/

		#ifdef DEBUGSEARCH
			addDebugMove(moveChoices.moves[i].m);
			printPositionToFile(&moveChoices,alpha, beta, score,true);
		#endif
		score=max(score,-ABqsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,*pos));
		#ifdef DEBUGSEARCH
			printPositionToFile(&moveChoices,alpha, beta, score,false);
			removeDebugMove();
		#endif
		if(score>=beta) return score;
	}
	return score;
}

/*ABqsearch()
 *a quiescence search which makes sure we have a quiet position to score
 *
 *@param alpha - lower bound
 *@param beta - upper bound
 *@param caputre - a capture move
 *@param pos - the parent board position
 *
 *@returns the move's quiesce score
 */
int ABqsearch(int alpha, int beta, move capture, board pos)
{
	int i;
	moveList moveChoices;
	int score;
	nodes++;
	if(makemove(&pos,capture)) //execute opponents caputre
		return INF; //return if illegal
	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	if(decidable(&pos,(drawEntry*)NULL,-1,&i)) //test the game-theoretical decidability of the current position
		return i;
	if(checkEvasions && inCheck(pos,pos.side)) //do check evasions
		return ABcheckEvasion(alpha,beta,&pos);
	score=eval(&pos);
	if(score>=beta) // test for "stand pat" cuttoff
		return score;
	generateGoodCaptures(&pos,&moveChoices);
	if(moveChoices.moveCount==0)
		return score;
	//follow promising captures
	for(i=0;i<moveChoices.moveCount;i++)
	{
		//Selective Futility Condition (material_balance+SEE(m)+qs_futility_margin <=alpha)
		/*if(pos.material + moveChoices.moves[i].score + QS_FUTIL_MARGIN <= alpha)
			break;*/
		#ifdef DEBUGSEARCH
			addDebugMove(moveChoices.moves[i].m);
			printPositionToFile(&moveChoices,alpha, beta, score,true);
		#endif
		score=max(score,-ABqsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,pos));
		#ifdef DEBUGSEARCH
			printPositionToFile(&moveChoices,alpha, beta, score,false);
			removeDebugMove();
		#endif
		if(score>=beta) return score;
	}
	return score;
}

/*ABcheckEvasion()
 *does an alphabeta checkevasion search
 *
 *@param pos   - the board position
 *@param alpha - lower bound (usually -INF)
 *@param beta  - upper bound (usually  INF)
 *
 *@returns the best scored move for the position for the specified depth
 */
int ABcheckEvasion(int alpha, int beta, board *pos)
{
	int i,illegalMoves=0;
	moveList moveChoices;
	int score=NEGINF,temp;
	nodes++;
	/*================REMOVE==================*/
	if(!(nodes&0x3FF) && timesUp())
	{
		stopSearch=true;
		longjmp(env, 0);
	}
	/*================REMOVE==================*/
	generateMoves(pos,&moveChoices);
	sort(&moveChoices);
	if(moveChoices.moveCount==0)
		return 0;
	for(i=0;i<moveChoices.moveCount;i++)
	{
		#ifdef DEBUGSEARCH
			addDebugMove(moveChoices.moves[i].m);
			printPositionToFile(&moveChoices,alpha, beta, score,true);
		#endif
		temp=-ABqsearch(-beta,-max(alpha,score),moveChoices.moves[i].m,*pos);
		#ifdef DEBUGSEARCH
			printPositionToFile(&moveChoices,alpha, beta, score,false);
			removeDebugMove();
		#endif
		if(temp==NEGINF)
		{
			illegalMoves++;
			continue;
		}
		score=max(score,temp);
		if(score>=beta) return score;
	}
	if(illegalMoves==moveChoices.moveCount)
		return -(MATE-500);
	return score;
}

/*startStaticSearch()
 *static search does a search on the position, not on a move
 *generates legal moves and returns a search result
 *it does not do pruning on the first ply
 *
 *@param alpha - lowerbound
 *@param beta  - upperbound
 *@param pos   - the board position
 *
 *@returns the score for that position
 */
int startStaticSearch(int alpha, int beta, board* pos, short depth, short dfr, drawEntry* drawTable)
{
	int i,illegalMoves=0;
	smove best; //keeps track of best move and score
	moveList moveChoices;
	U8 hashFlag=ALPHA;
	TTprobe tt_probe;
	bool tt_hit;
	bool fail_high=false;

	best.score=NEGINF;

	//Transposition Table

	tt_hit=probeTT(pos,&tt_probe);
	if(tt_hit)
	{
		//test the applicability of the cached score information
		if(depth<=tt_probe.depth)
		{
			//handle transposition-table results that are exact scores
			if(tt_probe.flag==EXACT)
				return tt_probe.score;
			//handle transposition-table results that are upper bounds
			else if(tt_probe.flag==ALPHA)
			{
				if(tt_probe.score<=alpha) return tt_probe.score;
				//lower beta and the best upper bound so far
				if(tt_probe.score<beta) beta=tt_probe.score;
				//if(tt_score<upper) upper=tt_score;
			}
			//handle transposition-table results that are lower bounds
			else if(tt_probe.flag==BETA)
			{
				//trasposition table fail-high cutoffs
				if(tt_probe.score>=beta) return tt_probe.score;
				//raise alpha and best score so far
				if(tt_probe.score>alpha) alpha=tt_probe.score;
				//if(tt_probe.score>best.score) best.score=tt_probe.score;
			}
		}
	}
	//else {...} entry not found in transposition tables

	generateMoves(pos,&moveChoices); //generate moves

	if(moveChoices.moveCount==0) //if there are no moves to make
		return 0;                //return a draw score

	//find hashed move and put it in the front
	if(tt_hit && tt_probe.m!=NULLMOVE)
		for(i=0;i<moveChoices.moveCount;i++)
			if(moveChoices.moves[i].m==tt_probe.m)
			{
				moveChoices.moves[i].score=INF;
				break;
			}
	sort(&moveChoices);

	for(i=0;i<moveChoices.moveCount;i++) //try each move and see if it is better than the previous ones
	{
		#ifdef DEBUGSEARCH
			addDebugMove(moveChoices.moves[i].m);
			printPositionToFile(&moveChoices,alpha, beta, best.score,true);
		#endif
		if(searchType==AB)
			moveChoices.moves[i].score=-alphabeta(-beta,-max(alpha,best.score),moveChoices.moves[i].m,*pos,depth-1,dfr+1,drawTable);
		else
			moveChoices.moves[i].score=-pvs(-beta,-max(alpha,best.score),moveChoices.moves[i].m,*pos,depth-1,dfr+1,drawTable);
		#ifdef DEBUGSEARCH
			printPositionToFile(&moveChoices,alpha, beta, best.score,false);
			removeDebugMove();
		#endif
		if(moveChoices.moves[i].score==NEGINF)
		{
			illegalMoves++;
			continue;
		}
		if(moveChoices.moves[i].score>best.score)
		{
			if(best.score>=alpha)
				hashFlag=EXACT;
			best=moveChoices.moves[i];
		}
		if(best.score>=beta)
		{
			recordTT(pos,best.m,best.score,BETA,depth,dfr);
			updateHH(best.m,depth);
			return best.score;
		}
	}
	if(illegalMoves==moveChoices.moveCount)
	{
		if(inCheck(*pos,pos->side))
			return -(MATE-dfr);
		return 0;
	}

	recordTT(pos,best.m,best.score,hashFlag,depth,dfr);
	updateHH(best.m,depth);
	return best.score;
}
